package com.xiyou.week04.dfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 51. N 皇后
 * <p>
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * @ClassName：SolveNQueens
 * @Author：西柚
 * @Date：2022/1/18 12:34 上午
 * @Versiion：1.0
 */
public class SolveNQueens {

    private List<Integer> p;
    private Integer n;
    private boolean[] used;
    private HashSet<Integer> usedPlus;
    private HashSet<Integer> usedMinus;
    private List<List<Integer>> ans;

    /**
     * 输入：n = 4
     * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
     * 解释：如上图所示，4 皇后问题存在两个不同的解法。
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        p = new ArrayList<Integer>();
        ans = new ArrayList<List<Integer>>();
        used = new boolean[n];
        usedPlus = new HashSet<Integer>();
        usedMinus = new HashSet<Integer>();
        this.n = n;

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            stringBuilder.append(".");
        }

        dfs(0);
        List<List<String>> result = new ArrayList<List<String>>();
        for (List<Integer> a : ans) {
            List<String> pattern = new ArrayList<String>();

            for (int row = 0; row < n; row++) {
                StringBuilder str = new StringBuilder(stringBuilder.toString());
                str.setCharAt(a.get(row), 'Q');
                pattern.add(str.toString());
            }
            result.add(pattern);
        }

        return result;
    }

    private void dfs(int row) {
        if (row == n) {
            ans.add(new ArrayList<Integer>(p));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!used[col] && !usedPlus.contains(row + col) && !usedMinus.contains(row - col)) {
                p.add(col);
                used[col] = true;
                usedPlus.add(row + col);
                usedMinus.add(row - col);
                dfs(row + 1);
                used[col] = false;
                usedPlus.remove(row + col);
                usedMinus.remove(row - col);
                p.remove(p.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        SolveNQueens solveNQueens = new SolveNQueens();
        System.out.println(solveNQueens.solveNQueens(4));
    }
}
